The present invention relates to a technique for color image processing and, more particularly, to error diffusion halftoning which correlates dots printed from different color planes and tones to create a more visually pleasing combination of different color dots and superior dot placement.
Images, such as charts, drawings, and pictures, may be represented as a two-dimensional matrix of picture elements (pixels). The spatial resolution and tone level for each pixel are chosen to correspond to the particular output device used. For example, typical computer monitors display images at 75 dots per inch (DPI) and have 256 levels of intensity for each color. Such monitors use the additive primary colors, red, green, and blue (RGB), which can be combined to produce millions of colors and also black.
Typical hardcopy output devices, such as inkjet printers, are binary devices, meaning that for each pixel or possible dot location on the printed medium they can only print at two levels: on or off. Therefore, some means must be provided to convert the monitor-based version of the image (256 tone levels per color), or another version of the color image, to the binary version (2 levels per color). These conversion methods are commonly referred to as halftoning. Halftoning methods are described in the book Digital Halftoning, by Robert Ulichney, The MIT Press, 1987, incorporated herein by reference.
One major approach to halftoning is error diffusion. The decision about whether or not to print a dot is based not only on the xe2x80x9cidealxe2x80x9d intensity (i.e., one of the 256 possible intensities) for that pixel, but on what has happened before for previously processed pixels.
It is assumed in the following explanation that there are 256 pixel intensities that range between 0 and 255. In conventional error diffusion, at each point where a dot may be printed, the original image pixel intensity between 0 to 255, plus accumulated error, is compared to a previously chosen threshold value. If the image pixel intensity is greater than the threshold value, a dot (255 intensity) is assigned to that pixel. If not, no dot (0 intensity) is assigned. In either case, the intensity difference between the actual dot value assigned (0 or 255) and the ideal image pixel intensity plus accumulated error for that point is derived, and this difference becomes an error term that is xe2x80x9cdiffusedxe2x80x9d to other subsequently processed pixels. In other words, the diffused error term is added to the image pixel intensity plus the accumulated error of other subsequently processed pixels, and this total resultant image pixel intensity is then compared against the error diffusion threshold to determine whether a dot should be printed. The parameters in error diffusion halftoning that have the most visual effects on the final outcome of the printed output are the thresholds, the error weightings and the direction of the error diffusion.
Typically, an error diffusion threshold value is static, e.g., 50 percent of the maximum theoretical image pixel intensity. For example, if there are 256 tone levels (0 to 255) per pixel, a level of 128 may be chosen as the threshold value. Improvements to the quality of the printed output may be achieved, however, by randomly varying the threshold value as described in Digital Halftoning, by Robert Ulichney, The MIT Press, 1987, page 265.
In addition, typical error diffusion techniques use constant weighting factors to compute the proportion of the error that is diffused to each surrounding pixel. A well known error diffusion technique is described by R. Floyd and L. Steinberg in the paper Adaptive Algorithm for Spatial Grey Scale, SID Int""l. Sym. Digest of Tech. Papers, pp. 36-37 (1975), incorporated herein by reference. The Floyd and Steinberg error diffusion technique diffuses the error into a set of four surrounding pixels. Error diffusion with higher than four terms can also be used. U.S. Pat. No. 5,313,287 to David Barton, assigned to the present assignee and incorporated herein by reference, discloses another error diffusion technique.
Another type of error diffusion method, known as tone dependent error diffusion, varies the error diffusion threshold value and/or the error weightings according to the tone or intensity of the pixel being processed. Tone dependent error diffusion is described in the articles xe2x80x9cReduction of Artifacts in Error Diffusion by Means of Input-Dependent Weights,xe2x80x9d by Eschbach, E., Journal of Electronic Imaging, vol. 2(4), October 1993, and xe2x80x9cAdaptive Filtering for Error Diffusion Quality Improvement,xe2x80x9d by Shu, J., SID Digest of Technical Papers, May 1995, as well as U.S. Pat. Nos. 5,737,453 and 5,757,976, all of which are incorporated herein by reference. Tone dependent error diffusion techniques are typically monochromatic.
When printing a color image, dots for multiple colors, such as cyan, magenta, and yellow, are printed in various combinations to achieve the desired color tones to reproduce the original color image. Many known error diffusion methods operate on one color plane (e.g., cyan, magenta, or yellow) at a time. These types of error diffusion methods strive to generate a visually pleasing pattern of dots (i.e., dispersed dots) for each separate color, independent of the pattern of dots for the remaining colors. Due to random chance, these overlapping color dot patterns inevitably result in two or more dots of different colors overlapping or being adjacent to one another, as shown in FIG. 1, which is perceived by the human eye as a clumping of dots.
FIG. 1 illustrates an example of a prior art multi-colored dot pattern using magenta dots 4 and cyan dots 6. The overall tone is light blue. When the cyan and magenta planes overlap, non-pleasing dot patterns due to adjacent cyan and magenta dots (such as at location 7) can be formed due to random chance.
Other known error diffusion methods operate on multiple color planes at the same time, which is known as plane dependency, such as the method described in U.S. application Ser. No. 08/880,475, entitled xe2x80x9cCorrelating Cyan and Magenta Planes for Error Diffusion Halftoningxe2x80x9d by Jay S. Gondek, filed Jun. 3, 1997, having the same assignee, and which is incorporated herein by reference. Multiple color planes, such as cyan and magenta, are correlated to create dot patterns that do not fall on top of one another up to a combined 100 percent fill. Consequently, the occurrence of darker xe2x80x9cbluexe2x80x9d dots (cyan overlapping magenta creates dark blue) is avoided, which also fills in white space that would otherwise contributed to the perception of graininess. Thus, a more visually pleasing patterning of dots is created.
FIG. 2 illustrates an example of a dot pattern of cyan and magenta dots printed using a plane dependent error diffusion method. As can be seen, FIG. 2 is an improvement over FIG. 1 because there are no adjacent or overlapping cyan and magenta dots.
However, as can be seen in FIG. 2, a drawback of plane dependent halftoning is that the relative spatial placement of the dots in light tones is not optimized. Consequently, in light or mid tones, patterns can develop in the printed output. These patterns occur because of the way the error can xe2x80x9ccascadexe2x80x9d through the image to produce curved lines of printed dots. These anomalies are often referred to as xe2x80x9cwormsxe2x80x9d because they can resemble small thin worms in the image.
As discussed above, while tone dependent error diffusion may be used to generate a pleasing pattern of dots, tone dependent error diffusion is monochromatic. Consequently, the use of tone dependent error diffusion with a color image results in an image that, while each color may independently have a pleasing pattern, when combined the colors randomly overlap.
Accordingly, there is a need for a color halftoning method that provides a printed output with the plurality of colors that are correlated so as to produce uniform patterning without unintentionally overlap of the colors.
The present invention provides a method and a system for processing an image composed of image pixels, each image pixel having a predetermined tone level. The method uses tone dependent plane dependent error diffusion halftoning to process the image for output on a digital output device, such as a printer. Tone dependent plane dependent error diffusion halftoning takes into account multiple color planes, such as cyan and magenta, when determining the placement of a dot in any of the color planes. The combined tone of the correlated color planes is used to determine the threshold levels against which the combined tone and the accumulated errors for the correlated color planes are compared. Further, tone dependent error weightings are determined based on the combined tones of the correlated color planes. The tone dependent error weightings are used to diffuse the final accumulated errors for each color plane. Using this technique, printed dots of two or more colors are dispersed so as to avoid noticeable clumping of dots to provide a more uniform pattern and to avoid the unintentional overlapping of colors.
The method determines whether to print zero dots, one dot of either correlated color plane, or two dots, for each pixel position. Two dots are printed if (1) the combined tones from the plane dependent colors are above a full intensity threshold (100 percent fill), i.e., the pixel has a tone value indicating that a dot must be printed; and (2) the combined tones and accumulated errors from the plane dependent colors are greater than a tone dependent threshold. The two dots that are printed are preferably not of the same color. One dot is printed if either (1) or (2) is true and no dots are printed if neither (1) nor (2) is true. Because the color planes are correlated, the printing of dots of the correlated colors has a reduced likelihood that the printed dots will unintentionally overlap.
Thus, the error diffusion takes into account the tone level of the pixel as well as multiple color planes when determining whether to print zero, one, or two dots to represent the pixel. This technique can be used to augment most existing error diffusion methods. In the preferred method, only correlation between the magenta and cyan color planes is performed, and no correlation with the yellow plane is performed. This is because the cyan and magenta planes are darker than the yellow, and adjacent or overlapping cyan and magenta dots are much more noticeable than a cyan or magenta dot adjacent to a yellow dot. However, correlation with three or more color planes may be performed using the techniques described herein.